package leetcode每日一题.leetcode20212.滑动窗口;

import java.util.HashMap;

/**
 * 字节跳动的面试原题(难题，有区分度)
 * 1. 问题描述
 *      给你一个字符串s 、一个字符串t 。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串 "" 。
 *      注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 2. 算法分析
 *      1. 暴力法 思路简单，代码容易实现，但是时间复杂度非常高 超出时间限制  不推荐
 *      2. 滑动窗口     代码中有详细的注释
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q004_最小覆盖子串 {

    /**
     * 暴力法  超出时间限制
     */
    public String minWindow1(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if(slen < tlen) {
            return "";
        }

        // 将字符串转化为字符数组
        char[] sarr = s.toCharArray();
        char[] tarr = s.toCharArray();

        // 对t进行hash计数
        HashMap<Character,Integer> tmap = new HashMap<>();
        for(int i = 0; i < tarr.length; i++) {
            if(!tmap.containsKey(tarr[i])) {
                tmap.put(tarr[i],1);
            } else {
                tmap.put(tarr[i],tmap.get(tarr[i]) + 1);
            }
        }

        // 创建s子串的hash 因为下面需要多次创建，所以将其提取出来，节省内存
        HashMap<Character,Integer> smap = new HashMap<>();

        // 我们只需要枚举s中长度大于等于t的子串，因为其余子串是不可能覆盖的
        // 子串长度的可能：tlen,tlen+1,tlen+2,....,tlen+k,其中tlen+k <= slen
        // 实际上我们枚举k即可：0,1,2,...,slen-tlen
        for(int k = 0; k <= slen - tlen; k++) {
            int curlen = k + tlen; // 当前寻找的子串长度
            for(int j = 0; j + curlen <= slen; j++) { // 枚举s串中长度为curlen的子串的起始索引
                // 记录以当前起始字符开始的长度为curlen的子串中字符出现的次数
                for(int i = j; i < j + curlen; j++) {
                    if(!smap.containsKey(sarr[i])) {
                        smap.put(sarr[i],1);
                    } else {
                        smap.put(sarr[i],smap.get(sarr[i]) + 1);
                    }
                }
                if(isCover(smap,tmap)) {
                    return s.substring(j,j+curlen);
                }
                smap.clear(); // 清空，进行下一次统计
            }
        }
        return "";
    }

    // 将s，t统计之后的hash表当做参数，判断两个字符串是否为覆盖关系
    // 由题意：s来覆盖t
    // 时间复杂度为:O(|s|)
    public boolean isCover(HashMap<Character,Integer> smap,HashMap<Character,Integer> tmap) {
        for(Character key : smap.keySet()) {
            if(smap.get(key) < tmap.get(key)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 滑动窗口法
     * @param s
     * @param t
     * @return
     */
    public String minWindow2(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if(slen == 0 || tlen == 0 || slen < tlen) {
            return "";
        }
        // 将字符串转化为字符数组
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();
        // 定义两个整型hash
        int[] shash = new int[128]; // 变动的
        int[] thash = new int[128]; // 固定的
        // 初始化thash
        for(Character ch : charArrayT) {
            thash[ch]++;
        }
        // 定义滑动窗口
        int left = 0;
        int right = 0;
        // 定义全局最小长度其满足覆盖要求的
        int minlen = slen + 1;
        // 定义编辑距离 distances的含义：窗口内字符出现在t中的次数，如果distances = tlen，表明当前找到了局部满足的子串
        int distances = 0; // 这个变量用来优化覆盖，可以将时间复杂度优化到O(1) 常用的技巧
        // 定义覆盖字串的起始索引
        int begin = 0;
        // 滑动部分代码(主要的逻辑代码)
        while(right < slen) {
            // 1. 判断当前右窗口的字符没有出现在t中
            if(thash[charArrayS[right]] == 0) { // 没有出现
                right++;
                continue;
            }
            // 2. 如果出现，修改编辑距离
            if(shash[charArrayS[right]] < thash[charArrayS[right]]) {
                distances++; // 距离自增
            }
            shash[charArrayS[right]]++;
            right++;
            // 3. 判断当前是否找到对应的子串
            while(distances == tlen) {
                // 如果此时找到，我们需要移动左窗口
                // 1. 由于当前找到了一个局部满足覆盖条件的子串，修改minlen和begin
                if(right - left < minlen) { // 当前找到的子串长度小于minlen
                    minlen = right - left;  // 修改全局最小
                    begin = left; // 修改起始索引
                }
                // 2. 判断当前需要移除的左窗口对应的字符是否出现在t中
                if(thash[charArrayS[left]] == 0) {
                    left++; // 此时distances是不需要修改的，因为移除的字符不在t中，不影响编辑距离
                    continue; // 然后直接跳过当前
                }
                // 3. 如果移除的字符出现在t中
                if(thash[charArrayS[left]] == shash[charArrayS[left]]) {
                    distances--;
                }
                shash[charArrayS[left]]--;
                left++;
            }
        }
        if(minlen == slen + 1) {
            return "";
        }
        return s.substring(begin,begin+minlen);
    }
}
